//
// Description: 70. 爬楼梯
// Created by Loading on 2025/4/4.
//

#include <bits/stdc++.h>

using namespace std;

int climbStairs(int n) {
    if (n == 1 || n == 2) {
        return n;
    }
    vector<int> v(n);
    v[0] = 1;
    v[1] = 2;
    for (int i = 2; i < n; ++i) {
        v[i] = v[i - 1] + v[i - 2];
    }

    return v[n -1];
}

int main() {
    int n = 45;

    auto res = climbStairs(n);

    cout << res << endl;

    return 0;
}
